#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define NUM 1024

int q[NUM];
int tt = 0;
int hh = 0;
  
void Printf(int* array, int size)
{
  for(int i = 0; i < size; i++){
    printf("%d ", array[i]);
  }

  printf("\n");
}

void Swap(int* pa1, int* pa2)
{
  int tmp = *pa1;
  *pa1 = *pa2;
  *pa2 = tmp;
}

int GetMidIndex(int* array, int left, int right)
{
  int mid = (left + right) >> 1;
  if(array[left] < array[mid]){
    if(array[left] > array[right]){
      return left;
    }
    else {
      if(array[mid] > array[right]){
        return right;
      }
      return mid;
    }
  }
  else {
    //left > mid
    if(array[mid] > array[right]){
      return mid;
    }
    else {
      if(array[left] > array[right]) return right;
      else return left;
    }
  }
}

//左右指针法
int Part1(int* array, int left, int right)
{
    int begin = left;
    int end = right;

    Swap(&array[begin], &array[GetMidIndex(array, begin, end)]);
    int keyi = begin;
    while(begin < end){
      while(begin < end && array[end] >= array[keyi]) end--;
      while(begin < end && array[begin] <= array[keyi]) begin++;
      if(begin < end) Swap(&array[begin], &array[end]);
      else {
        Swap(&array[begin], &array[keyi]);
      }
    }

    return begin;
}

int Part2(int* array, int left, int right)
{

}

int Part3(int* array, int left, int right)
{

}

void NonRQuickSort(int* array, int size)
{
  //左右边界入队
  q[tt++] = 0;
  q[tt++] = size - 1;

  while(hh < tt){
    int left = q[hh++];
    int right = q[hh++];

    int meeti = Part1(array, left, right);
    //设置边界，入队
    if(left < meeti - 1){
      q[tt++] = left;
      q[tt++] = meeti - 1;
    }
    if(meeti + 1 < right){
      q[tt++] = meeti + 1;
      q[tt++] = right;
    }
  }
}

void TestNonRQuickSort()
{
  int* array = (int*)malloc(sizeof(int) * 100);
  if(array == NULL){
    perror("malloc");
    return ;
  }

  for(int i = 0; i < 100; i++){
    array[i] = rand() % 100 + 1;
  }

  NonRQuickSort(array, 100);
  Printf(array, 100);
  free(array);
}

int main()
{
  srand((unsigned long)time(NULL));
  TestNonRQuickSort();
  return 0;
}
